#include<vector>
#include<algorithm>


namespace xyx
{
    //仿函数
    template<class T>
    class Less
    {
    public:
        bool operator()(const T& x,const T& y)
        {
            return x < y;
        }
    };
    
    template<class T,class Container = vector<T>, class Compare = Less<T>>
    class priority_queue
    {
    public:
        template<class Input_Iterator>
        priority_queue(Input_Iterator first, Input_Iterator last)
        {
            while(first != last)
            {
                con.push_back(*first);
                ++first;
                adjustup(con.size()-1);
            }
        }
        
        priority_queue(){}
        
        void adjustdown(int parent)
        {
            Compare com;
            int child = (parent + 1) * 2;
            while(child < con.size())
            {
                if(child + 1 < con.size() && com(con[child],con[child+1]))
                    child++;
                if(child < con.size() && com(con[parent],con[child]))
                {
                    swap(con[parent],con[child]);
                    parent = child;
                    child = (parent + 1) * 2;
                }
                else
                {
                    break;
                }
            }
        }
        
        void adjustup(int child)
        {
            Compare com;
            int parent = (child - 1 - 1) / 2;
            while(child < 0)
            {
                if(parent >= 0 && com(con[parent],con[child]))
                {
                    swap(con[parent],con[child]);
                    child = parent;
                    parent = (child - 1 - 1) / 2;
                }
                else
                {
                    break;
                }
            }
        }
      
        void push(const T& x)
        {
            con.push_back(x);
            adjustup(con.size()-1);
        }
        
        void pop()
        {
            swap(con[0],con[con.size()-1]);
            con.pop_back();
            adjustdown(0);
        }
        
        T& top()
        {
            return con.front();
        }
        
        bool empty()
        {
            return con.empty();
        }
        
    private:
        Container con;
    };

    void test_pq()
    {
        priority_queue<int> pq;
        
        pq.push(5);
        pq.push(1);
        cout << pq.top() << endl;;
        pq.push(4);
        pq.empty();
        pq.pop();
        pq.push(2);
        pq.push(3);
        
        while(!pq.empty())
        {
            cout << pq.top() << " ";
            pq.pop();
        }
        cout << endl;
        
    }

    void test_pq1()
    {
        vector<int> nums;
        nums.push_back(5);
        nums.push_back(1);
        nums.push_back(3);
        nums.push_back(4);
        nums.push_back(2);
        
        priority_queue<int> pq(nums.begin(),nums.end());
        
        while(!pq.empty())
        {
            cout << pq.top() << " ";
            pq.pop();
        }
        cout << endl;
        
    }
}
